package leetcode.editor.cn;

import java.util.Scanner;

/**
题目名字---:反转链表
题目编号---:206	
*/

public class ReverseLinkedList{
    public static void main(String[] args) {
        ReverseLinkedList reverseLinkedList = new ReverseLinkedList();
        //创建一个常数值链表
        ListNode head3 = reverseLinkedList.createLinkedList3();
        ListNode node = reverseLinkedList.reverseList1(head3);

        ListNode head2 = reverseLinkedList.createLinkedList2();
        ListNode head = reverseLinkedList.createLinkedList();
        ListNode listNode = reverseLinkedList.reverseList1(head);
    }
    /**
     * 创建一个常数值链表
     */
    public ListNode createLinkedList3() {
        ListNode head =null;
        ListNode prev =null;
        for (int i = 0; i < 5; i++) {
            ListNode node = new ListNode(i + 1);
            if (head == null) {
                head = node;
                prev = head;
            }else {
                prev.next = node;
                prev = prev.next;
            }
        }
        return head;
    }
    /**
     * 尾插法创建链表
     * @return
     */
    public ListNode createLinkedList2() {
        ListNode head = null ;
        ListNode prev = null;
        Scanner scanner = new Scanner(System.in);
        int nextInt;
        nextInt = scanner.nextInt();
        while (nextInt!=-1000) {
            ListNode node = new ListNode(nextInt);
            if (head == null) {
                head = node;
                prev = node;
                node.next = null;
            }else {
                prev.next = node;
                node.next = null;
                prev = prev.next;
            }
            nextInt = scanner.nextInt();
        }
        return head;
    }
    /**
     * 迭代法创建链表
     * @return
     */
    public ListNode createLinkedList() {
        ListNode head = new ListNode();
        ListNode prev = null;
        Scanner scanner = new Scanner(System.in);
        int nextInt;
        nextInt = scanner.nextInt();
        while (nextInt!=-1000) {
            ListNode node = new ListNode(nextInt);
            prev = head.next;
            head.next = node;
            node.next = prev;
            nextInt = scanner.nextInt();
        }
        return head;
    }

    /**
     * 递归反转链表
     * @param head
     * @return
     */
    public ListNode reverseList1(ListNode head) {
        if (head==null||head.next==null) {
            return head;
        }
        ListNode lastNode = reverseList1(head.next);
        head.next.next =head;
        head.next=null;
        return lastNode;
    }

    /**
     * 迭代反转链表
     * @param head
     * @return
     */
    public ListNode reverseList2(ListNode head) {
        ListNode curr = head;
        ListNode prev = null;
        while (curr!=null) {
            ListNode next = curr.next;
            curr.next = prev ;
            prev = curr;
            curr = next;
        }
        return prev;
    }
    public ListNode reverseList3(ListNode head) {
        if (head==null||head.next==null) {
            return head;
        }
        ListNode listNode = reverseList3(head.next);
        head.next.next = head;
        head.next =  null;
        return listNode;
    }

//leetcode submit region begin(Prohibit modification and deletion)
class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head==null||head.next==null) {
            return head;
        }
        ListNode lastNode = reverseList1(head.next);
        head.next.next =head;
        head.next=null;
        return lastNode;
    }
}
}